package 力扣;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-09-11
 * Time: 14:06
 */
public class minimum_cost_to_hire_k_workers {
    public static double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int len = quality.length;
        Integer[] q = new Integer[len];
        for(int i = 0; i < len; i++){
            q[i] = i;
        }
        //按照单位工资期望从小到大进行排序
        // Arrays.sort(q, (a, b) -> {
        //     return (int)(wage[q[a]] * 1.0 / quality[q[a]] - wage[q[b]] * 1.0 / quality[q[b]] + 0.5);
        // });
        Arrays.sort(q, (a, b) -> {
            return quality[b] * wage[a] - quality[a] * wage[b];
        });
        //这里需要建立一个大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> {
            return b - a;
        });
        int quality_sum = 0;
        double res = 1e9;
        for(int i = 0; i < len; i++){
            double untiWage = wage[q[i]] * 1.0 / quality[q[i]];
            quality_sum += quality[q[i]];
            while(queue.size() > k - 1){
                quality_sum -= queue.poll();
            }
            if(queue.size() == k - 1){
                res = Math.min(res, quality_sum * untiWage);
            }
            queue.offer(quality[q[i]]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] quality = {10,20,5};
        int[] wage = {70,50,30};
        mincostToHireWorkers(quality, wage, 2);
    }
}
